#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/9/11 17:33
# @Author  : Yuyun
# @File    : 生成哈夫曼树.py
# @IDE     : PyCharm

"""
给定长度为n的无序的数字数组，每个数字代表二叉树的叶子节点的权值，数字数组的值均大于等于1。
请完成一个函数，根据输入的数字数组，生成哈夫曼树，并将哈夫曼树按照中序遍历输出。

为了保证输出的二叉树中序遍历结果统一，增加以下限制：
二叉树节点中，左节点权值小于等于右节点权值，
根节点权值为左右节点权值之和。
当左右节点权值相同时，左子树高度高度小于等于右子树。

注意：所有用例保证有效，并能生成哈夫曼树。

提醒：哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。
所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度
（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。
"""
class TreeNode:
    def __init__(self, weight, left = None, right = None):
        self.weight = weight
        self.left = left
        self.right = right
        self.height = 1
    #   递归计算节点的高度
    def get_height(self):
        if not self.left and not self.right:
            return 1
        left_height = self.left.get_height() if self.left else 0
        right_height = self.right.get_height() if self.right else 0
        return 1 + max(left_height, right_height)
    #   重写方法，基于节点的权重进行比较。这解决了 heapq 无法比较 Node 实例的问题
    def __lt__(self, other):
        return self.weight < other.weight
import heapq
class Solution:
    def build_huffman_tree(self, weights):
        # 初始化最小堆，创建叶子节点
        heap = [TreeNode(weight) for weight in weights]
        heapq.heapify(heap)
        while len(heap) > 1:
            # 取出两个权值最小的节点
            left = heapq.heappop(heap)
            right = heapq.heappop(heap)
            # 如果权值相同，按照高度进行处理
            if left.weight == right.weight:
                left_height = left.get_height()
                right_height = right.get_height()
                # 确保左子树高度 <= 右子树高度
                if left_height > right_height:
                    left, right = right, left
            # 创建新的父节点，权值为左右节点权值之和
            merged_node = TreeNode(left.weight + right.weight, left, right)
            heapq.heappush(heap, merged_node)
        # 返回堆中唯一的节点，即哈夫曼树的根节点
        return heap[0]
    #   栈迭代法进行中序遍历
    def midorder_traversal(self, root:TreeNode):
        res = []
        if root is None:
            return
        stack = [root]
        while stack:
            node = stack.pop()
            if node != None:
                #   按照顺序压栈：右节点、中节点、左节点
                if node.right:
                    stack.append(node.right)
                stack.append(node)
                #   中节点访问过，但是还没有处理，加入空节点做为标记。
                stack.append(None)
                if node.left:
                    stack.append(node.left)
            #  只有遇到空节点的时候，才将下一个节点放进结果集
            else:
                #   按照左节点、中节点、右节点出栈
                node = stack.pop()
                res.append(node.weight)
        return res
    #   递归法进行中序遍历
    def midorder_traversal_I(self, root:TreeNode):
        res = []
        def dfs(node):
            if node is None:
                return
            dfs(node.left)
            res.append(node.weight)
            dfs(node.right)
        dfs(root)
        return res
    #   递归法简化写法
    def midorder_traversal_II(self, root:TreeNode):
        if root is None:
            return []
        return self.midorder_traversal_II(root.left) + [root.weight] + self.midorder_traversal_II(root.right)

if __name__=='__main__':
    weights = list(map(int, input().split(',')))
    solution = Solution()
    huffman_tree = solution.build_huffman_tree(weights)
    result = solution.midorder_traversal(huffman_tree)
    print(result)

"""
class TreeNode:
    def __init__(self, weight, left = None, right = None):
        self.weight = weight
        self.left = left
        self.right = right
        self.height = 1
    # 递归计算节点的高度
    def get_height(self):
        if not self.left and not self.right:
            return 1
        left_height = self.left.get_height() if self.left else 0
        right_height = self.right.get_height() if self.right else 0
        return 1 + max(left_height, right_height)
import heapq
class Solution:
    def build_huffman_tree(self, weights):
        pr_queue = []
        queue = []
        for weight in weights:
            #   当左右节点权值相同时，(weight, TreeNode(weight))的堆元素格式可确保左子树高度高度小于等于右子树
            heapq.heappush(pr_queue, weight)
        while len(pr_queue) > 1:
            #   左节点权值小于等于右节点权值，小顶堆弹出第一个元素为left，第二个为right
            left_weight = heapq.heappop(pr_queue)
            left = TreeNode(left_weight)

            right_weight = heapq.heappop(pr_queue)
            right = TreeNode(left_weight)

            # 如果权值相同，按照高度进行处理
            if left.weight == right.weight:
                left_height = left.get_height()
                right_height = right.get_height()
                # 交换，确保左子树高度 <= 右子树高度，
                if left_height > right_height:
                    left, right = right, left
            #   父节点为权值为左右节点权值之和。
            father_node = TreeNode(left_weight + right_weight, left, right)
            queue.append(left)
            queue.append(right)
            queue.append(father_node)
            heapq.heappush(pr_queue,father_node.weight)
        root = queue.pop()
        #   队列中剩下的就是根节点
        return root

    def midorder_traversal(self, root:TreeNode):
        res = []
        if root is None:
            return
        stack = [root]
        while stack:
            node = stack.pop()
            if node != None:
                #   按照顺序压栈：右节点、中节点、左节点
                if node.right:
                    stack.append(node.right)
                stack.append(node)
                #   中节点访问过，但是还没有处理，加入空节点做为标记。
                stack.append(None)
                if node.left:
                    stack.append(node.left)
            #  只有遇到空节点的时候，才将下一个节点放进结果集
            else:
                #   按照左节点、中节点、右节点出栈
                node = stack.pop()
                res.append(node.weight)
        return res

if __name__=='__main__':
    weights = list(map(int, input().split(',')))
    solution = Solution()
    huffman_tree = solution.build_huffman_tree(weights)
    result = solution.midorder_traversal(huffman_tree)
    print(result)

"""